Feature #6: Maximum Users

Description#

On a busy intersection with heavy vehicular and pedestrian traffic, the operator deploys a base station. The number of users connected to that base station keeps changing rapidly, as people enter and leave its coverage area. The base station quickly dumps the current number of users to a list every 1 ms.

The operator wants to analyze the data to improve coverage for its users. However, the data contains rapid variations that don’t carry useful information from a network management perspective. To deal with the variation, the operator wants to find the maximum number of users connected to the base station in every k ms sliding window.

Given a list of values, we need to create a sliding window of size k (shown in red) and find the max in each sliding window. Different sliding windows in the given list are shown in separate rows in the following illustration, along with the maximum value in the sliding window.

Solution#

Here, we will find the maximum number of users who are connected to the base station in the selected k millisecond windows. Each entry in the array will show the number of users who are connected to the base station in the 1 ms window.

Here is how we will implement this feature:

1. We are given an array of integers.

2. If the value at the current index is less than the value at the previous index of the array or all the value(s) of the index(es) in mqueue, then we will push the current index to the mqueue. Otherwise, we will perform the pop operation.

3. During the loop execution, if the mqueue value (index) at zero index is equal to the i-k, then we will perform the shift operation in the mqueue.

4. If the index of the given array is greater than or equal to the window slide length (k), then we will push the maximum value of the mqueue to the result array.

This way, the result array will contain the maximum number for each window slide (k).

The following illustrations show us how the solution given above will work:

Let’s look at the solution code below:

Complexity measures#

Time complexity#

Here, we are iterating the outer for loop n times and the inner while loop k times. Here, n is the size of the given array, and k is the size of the sliding window, which is constant. Therefore, the time complexity will be $O(n)$.

Space complexity#

The space complexity will be $O(k)$, because we need to store a maximum of k values in the mqueue.